#include <bits/stdc++.h>

#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;

template < typename T > T read() {
	T x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int N = 1e5 + 10;

int a[N], n, Q, lst[N << 1];
ll ans[N];
veg pot[N];

namespace seg {
	const int N = 4e5 + 10;
	ll tg[N], htg[N], hmx[N], mx[N];
	void pu(int x) { mx[x] = max(mx[x << 1], mx[x << 1 | 1]); hmx[x] = max(hmx[x << 1], hmx[x << 1 | 1]); }
	void pt(int x, ll t1, ll t2) {
		chkmax(htg[x], tg[x] + t2); chkmax(hmx[x], mx[x] + t2);
		tg[x] += t1; mx[x] += t1;
	}
	void pd(int x) {
		if(tg[x] || htg[x]) {
			pt(x << 1, tg[x], htg[x]);
			pt(x << 1 | 1, tg[x], htg[x]);
			tg[x] = htg[x] = 0;
		}
	}
	void upd(int xl, int xr, ll v, int o = 1, int l = 1, int r = n) {
		if(xl == l && xr == r) return pt(o, v, max(v, 0ll)); int mid = l + r >> 1; pd(o);
		if(xr <= mid) upd(xl, xr, v, o << 1, l, mid); else if(xl > mid) upd(xl, xr, v, o << 1 | 1, mid + 1, r);
		else upd(xl, mid, v, o << 1, l, mid), upd(mid + 1, xr, v, o << 1 | 1, mid + 1, r);
		pu(o);
	}
	ll query(int xl, int xr, int o = 1, int l = 1, int r = n) {
		if(xl == l && xr == r) return hmx[o]; int mid = l + r >> 1; pd(o);
		if(xr <= mid) return query(xl, xr, o << 1, l, mid); else if(xl > mid) return query(xl, xr, o << 1 | 1, mid + 1, r);
		else return max(query(xl, mid, o << 1, l, mid), query(mid + 1, xr, o << 1 | 1, mid + 1, r));
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	n = in; rep(i, 1, n) a[i] = in;
	Q = in; rep(i, 1, Q) { int l = in, r = in; pot[r].eb(l, i); }
	rep(i, 1, n) {
		seg :: upd(lst[a[i] + N] + 1, i, a[i]); lst[a[i] + N] = i;
		for(auto v : pot[i]) ans[v.se] = seg :: query(v.fi, i); 
	} rep(i, 1, Q) printf("%lld\n", ans[i]);
	return 0;
}
